Field of the Invention
The present invention relates to a high speed synchronous processing system for executing a parallel processing of programs having loops by a plurality of computers.
When a loop in a program is parallel-executed by a plurality of computers, each iteration of the loop is executed by a respective computer. In this case, if an operation performed by the computers is not synchronized, a true or correct execution will often not occur.
For example, the case where a parallel processing of a DO loop described by the FORTRAN programming language is executed often requires synchronization between computers. In general, when a parallel processing of a general purpose program is executed, a parallel processing of a loop can be easily executed.
A parallel (processing) execution image of an original program for a serial or sequential execution is represented or contained in each of the computers performing the parallel processing. The parallel execution image is as follows. That is, each iteration of a loop is executed by every execution unit in the parallel processing, and a processing thereof is parallel-executed by two or more computers. For this reason, when utilizing a parity of loop parameters, the image is divided into procedures by a cyclic distribution mode.
When a parallel processing of a procedure is executed, for example, before an assignment statement assigned into A(I+1) at I=1 in a procedure for a first computer-1 is executed, if a reference of A(I) at I=2 in a procedure for a second computer-2 is made, then an execution result obtained in the parallel processing is different from that of a sequential execution program.
Thus, procedures to effect or permit synchronous processing (e.g., post, wait) are provided between each execution image, to warrant or ensure a correct execution result. Syn #1 and syn #2 are variables used for a synchronous processing, that is synchronous variables, and take three kinds of values, "posted", "waiting" and "cleared". The labels or words (post), (wait), and (reset) denote procedures for utilizing the synchronous variables to effect a synchronous processing. (Wait) denotes a procedure that, if a value of a synchronous variable given as an argument is not "posted", the value of the variable is changed to "waiting" and then the continuation of processing is kept on inactive or suspended until the value is changed to "posted". (Post) denotes a procedure such that the value of a synchronous variable of an argument is reduced or changed to "posted" and the execution of the inactive procedure is restarted. (Reset) denotes a procedure that, when the value of a synchronous variable is equal to "posted", the value is changed to "cleared".
When the procedures are parallel-executed, each procedure of (post), (wait) and (reset) is executed during each iteration of a loop, and the operation of synchronization is carried out at a synchronization point (at a time of the (wait) procedure).
In a conventional method, synchronous variable syn #1 and syn #2 are required to be shared with the two computers. From this method, conversely, the two computers are able to effect or perform a reference operation and a change operation at the same time on each synchronous variable. In this case, the relevant synchronous variables are destructible or may be incorrectly changed and as a result, a true or correct processing is impossible to achieve.
Therefore, it is necessary to carry out indivisibly or separately the processings such as a reference of a synchronous variable, a pause instruction of a procedure and a restart of the procedure. For this reason, a special hardware instruction for synchronous processing (for example, a time-sharing instruction) is utilized.
Nevertheless, it is a characteristic that this kind of instruction has a longer run duration or takes longer to execute than a general instruction. Thus, a frequent overhead occurs due to a great deal (every iteration) of (post), (wait) and (reset) of processings, which could be considered a problem. Thus, in spite of the execution of a parallel processing, a shortening or reducing of running time does not work out satisfactorily, thereby causing yet another problem.
Therefore, realization of a synchronous processing by means of a combination of general instructions, is widely required in the field of a high speed synchronous processing in a loop parallel computation to reduce the overhead during a synchronous parallel processing or to realize a high speed synchronous processing. Thus, high speed data processing by means of an execution of parallel computation is achieved utilizing a combination of general instructions.